/**
 * 
 */
package _general.lefttree;

import java.util.Comparator;
import java.util.EnumMap;
import java.util.Map;

class Node<E> {

	/**
	 * Defines which kind of children nodes can have.
	 * 
	 * @author Michael Schmei&szlig;er
	 */
	static enum ChildType {
		LEFT, RIGHT;
	}

	/**
	 * Creates a new Node and returns it.
	 * 
	 * @param <E>
	 *            The type of content in this node
	 * @param parent
	 *            The parent node of the node to create, may be <b>null</b>
	 * @param where
	 *            Where to attach the created node to the parent node - doesn't
	 *            matter if parent is null
	 * @param content
	 *            The content of the node to create
	 * @return The newly created node
	 */
	static <E> Node<E> create(Node<E> parent, ChildType where, E content) {
		final Node<E> newChild = new Node<E>(parent, content);
		if (parent != null) {
			parent.children.put(where, newChild);
			if (where == ChildType.RIGHT) {
				parent.depth++;
			}
		}
		return newChild;
	}

	static <E> Node<E> merge(final Node<E> a, final Node<E> b,
			final Comparator<? super E> comparator) {
		if (a == null) {
			return b;
		} else if (b == null) {
			return a;
		}

		if (comparator.compare(a.getContent(), b.getContent()) > 0) {
			return merge(b, a, comparator);
		}

		merge(a.getChild(ChildType.RIGHT), b, comparator).attachToParent(a,
				ChildType.RIGHT, false);
		if (a.getChildDepth(ChildType.RIGHT) > a.getChildDepth(ChildType.LEFT)) {
			a.rotateChildrenRight();
		}
		return a;
	}

	private final E content;

	private EnumMap<Node.ChildType, Node<E>> children = new EnumMap<Node.ChildType, Node<E>>(
			Node.ChildType.class);

	private Node<E> parent = null;

	private int depth = 0;

	private Node(Node<E> parent, E content) {
		this.content = content;
	}

	void attachToParent(Node<E> newParent, ChildType where,
			boolean replaceNullOnly) {
		if (replaceNullOnly && newParent.children.containsKey(where)) {
			throw new IllegalStateException("This parent contains a " + where
					+ " child yet and replaceNullOnly is true");
		}
		this.detachFromParent();
		this.parent = newParent;
		newParent.children.put(where, this);
		newParent.recalculateDepth();
	}

	void detachFromParent() {
		if (this.parent == null) {
			return;
		}
		Node<E> currentNode = this.parent;
		for (Map.Entry<ChildType, Node<E>> entry : this.parent.children
				.entrySet()) {
			if (entry.getValue().equals(this)) {
				this.parent.children.remove(entry.getKey());
			}
		}
		this.parent.recalculateDepth();
		this.parent = null;

		while (currentNode != null) {
			if (currentNode.getChildDepth(ChildType.RIGHT) > currentNode
					.getChildDepth(ChildType.LEFT)) {
				currentNode.rotateChildrenRight();
			}
			currentNode = currentNode.parent;
		}
	}

	Node<E> getChild(ChildType whichChild) {
		return this.children.get(whichChild);
	}

	private int getChildDepth(ChildType which) {
		if (this.children.containsKey(which)) {
			return this.children.get(which).depth;
		}
		return -1;
	}

	E getContent() {
		return this.content;
	}

	Node<E> getParent() {
		return this.parent;
	}

	Node<E> mergeWith(Node<E> treeToMergeWith, Comparator<? super E> comparator) {
		return merge(this, treeToMergeWith, comparator);
	}

	private void recalculateDepth() {
		this.depth = this.getChildDepth(ChildType.RIGHT) + 1;
	}

	private void rotateChildrenRight() {
		final ChildType[] childTypes = ChildType.values();
		Node<E> valueAssociatedWithLeftNeighbor = this.children
				.get(childTypes[childTypes.length - 1]);
		for (int i = 0; i < childTypes.length; i++) {
			if (valueAssociatedWithLeftNeighbor == null) {
				valueAssociatedWithLeftNeighbor = this.children
						.remove(childTypes[i]);
			} else {
				valueAssociatedWithLeftNeighbor = this.children.put(
						childTypes[i], valueAssociatedWithLeftNeighbor);
			}
		}
		this.recalculateDepth();
	}

	@Override
	public String toString() {
		final StringBuilder resultBuilder = new StringBuilder();
		resultBuilder.append(this.getContent());
		resultBuilder.append('[');
		resultBuilder.append(this.getChild(ChildType.LEFT));
		resultBuilder.append(',');
		resultBuilder.append(this.getChild(ChildType.RIGHT));
		resultBuilder.append(']');
		return resultBuilder.toString();
	}
}